package it.luigiarpino.kernighanLin.bipartition;

public class HeapSorter
{
	private int heapSize;
	private int[] A;
	private int[] index;
	
	public static void main(String[] args)
	{
		int[] vettore = new int[]{ 0,2,1,4,3,5,6};
		int[] vettIndex = new int[]{ 0,1,2,3,4,5,6};
		HeapSorter hs=new HeapSorter(vettore, vettIndex);
		int[] result = hs.getVettore();
		int[] index = hs.getIndici();
		for(int i=0; i<result.length; i++)
		{
			System.out.print(" "+result[i]);
		}
		System.out.println();
		for(int i=0; i<result.length; i++)
		{
			System.out.print(" "+index[i]);
		}
		System.out.println();
	}
	
	public HeapSorter(int[] vettA, int[] vettIndex)
	{
		this.A=new int[vettA.length];
		this.index=new int[vettA.length];
		this.heapSize=vettA.length;
		for(int i=0; i<vettA.length; i++)
		{
			this.A[i]=vettA[i];
			this.index[i]=vettIndex[i];
		}
		this.buildHeap();
		for(int i=this.A.length-1; i>0; i--)
		{
			// Scambia A[0] con A[i]
			int tmp=this.A[0];
			this.A[0]=this.A[i];
			this.A[i]=tmp;
			int tmpIndex=this.index[0];
			this.index[0]=this.index[i];
			this.index[i]=tmpIndex;
			this.heapSize --;
			this.heapify(0);
		}
	}
	
	private int getLeft(int i)
	{
		/*
		i++;
		i=2*i;
		i--;
		return i;
		*/
		return (2*i)+1;
	}
	
	private int getRight(int i)
	{
		/*
		i++;
		i=(2*i)+1;
		i--;
		return i;
		*/
		return 2*(i+1);
	}
	
	/*
	private int getParent(int i)
	{
		i++;
		i=i/2;
		i--;
		return i;
	}
	*/
	
	private void heapify(int i)
	{
		//int l=getLeft(i);
		//int r=getRight(i);
		int l = (2*i)+1;
		int r = 2*(i+1);
		int largest;
		if ( (l<this.heapSize) && (A[l]>A[i]))
		{
			largest=l;
		}
		else
		{
			largest=i;
		}
		if ( (r<this.heapSize)&&(A[r]>A[largest]) )
		{
			largest=r;
		}
		if (largest != i)
		{
			// Swap
			int tmp=A[i];
			A[i]=A[largest];
			A[largest]=tmp;
			int tmpIndex=this.index[i];
			this.index[i]=this.index[largest];
			this.index[largest]=tmpIndex;
			this.heapify(largest);
		}
	}
	
	private void buildHeap()
	{
		this.heapSize=A.length;
		int l=(this.heapSize/2)-1;
		for(int i=l; i>=0; i--)
		{
			this.heapify(i);
		}
	}
	
	
	public int[] getVettore()
	{
		return A;
	}
	
	public int[] getIndici()
	{
		return index;
	}
	
}
